#include <iostream>

using namespace std;

const int N = int (1e4 + 10);

int Next[N];

void Get_Next(const char* cmp)
{
    Next[0] = -1;
    int k = -1, j = 0;

    while (cmp[j + 1]) // 不用去到最后一个元素处
    {
        if (k == -1 || cmp[k] == cmp[j])
        {
            k++, j++;
            if (cmp[k] == cmp[j]) 
                Next[j] = Next[k];
            else Next[j] = k;
        }
        else
            k = Next[k];
    }
}

int Str_Str(const char* str, const char* cmp)
{
    Get_Next(cmp);
    int i = 0, j = 0;
    while (j == -1 || str[i] && cmp[j])
    {
        if (j == -1 || str[i] == cmp[j])
        {
            j++, i++;
        }
        else
            j = Next[j];
    }
    if (cmp[j] == '\0') // 当 c == "\0" 时也会执行
        return i - j;
    return -1;
}

void Get_Next(const string& cmp)
{
    Next[0] = -1;
    int k = -1, j = 0;

    while (j != cmp.size() - 1) // 不用去到最后一个元素处
    {
        if (k == -1 || cmp[k] == cmp[j])
        {
            k++, j++;
            if (cmp[k] == cmp[j]) 
                Next[j] = Next[k];
            else Next[j] = k;
        }
        else
            k = Next[k];
    }
}

int Str_Str(const string& str, const string& cmp)
{
    Get_Next(cmp);
    int i = 0, j = 0;
    while (i != str.size() && j != cmp.size())
    {
        if (j == -1 || str[i] == cmp[j])
        {
            j++, i++;
        }
        else
            j = Next[j];
    }
    if (cmp[j] == '\0') // 当 c == "\0" 时也会执行
        return i - j;
    return -1;
}

class Solution {
public:
    int strStr(string haystack, string needle) {
        return Str_Str(haystack, needle);
    }
};